package b;

import java.util.ArrayList;
import java.util.List;

/**
 * @desc 平衡二叉树的实现，在插入和删除过程中树保持平衡。
 * @author hongxingfan
 * @scene 有一个user的集合，初始构建二叉平衡树，在不断插入和删除过程中有一个守护线程保持树平衡
 */
public class AVLTree {

	public static void main(String[] args) {
		User root = null;

		User u1 = new User(10);
		User u2 = new User(11);
		User u3 = new User(12);
		User u4 = new User(13);
		User u5 = new User(14);
		User u6 = new User(18);
		User u7 = new User(25);
		User u8 = new User(30);

		List<User> list = new ArrayList<User>();
		list.add(u1);
		list.add(u2);
		list.add(u3);
		list.add(u4);
		list.add(u5);
		list.add(u6);
		list.add(u7);
		list.add(u8);

		for(User u : list){
			if(root == null){
				root = u;
				continue;
			}
			// 比左子树小
			while(root != null){
				if(u.age < root.left.age)
					root = root.left;
				else if(u.age > root.right.age)
					root = root.right;
			}
		}
	}
}

class User {
	int age;
	User left;
	User right;

	public User(int age) {
		this.age = age;
	}
}